package models;

/**
 * 	Algoritmo de busca rápida em Strings - Boyer-Moore
 * @author Felipe
 * @author Diego
 * @author Rafael
 *
 */


public class Boyer_Moore {
	
	/**
	 * Texto onde será procurada a palavra.
	 */
	public String t;	// String do texto
	
	/**
	 * Palavra a ser procurada no texto.
	 */
	public String p;	//	String do padrão
	
	/**
	 * Tabela do alfabeto, neste caso tabela ASCII(correspondendo as teclas), que guardará
	 * os indices de onde os elementos se encontram no padrão ou -1 caso não se encontrem no padrão.
	 */
	public int l[];		//Tabela do alfabeto
	
	/**
	 * Tamanho do texto no qual será procurado o Padrão.
	 */
	public int n;		// Tamanho do texto
	
	/**
	 * Tamanho do Padrão que será procurado no texto.
	 */
	public int m;		// Tamanho do padrão
	

	
	/**
	 * <p> <strong> Construtor </strong> </p>
	 * 
	 * <p>	Construtor do algoritmo de Boyer-Moore, tem a função de inicializar
	 * as Strings e tamanhos do texto e padrão, e inicializar a tabela do alfabeto.
	 * </p>
	 * @param t Texto String na qual será procurado o padrão;
	 * @param p	Padrão String que será procurada no texto.
	 */
	public Boyer_Moore( String t, String p ){	//Construtor
		this.t = t;
		this.p = p;
		this.n = t.length();
		this.m = p.length();
		this.l = new int [256];
	}
	
	/**
	 * <p> <strong> Preprocessamento da tabela do alfabeto </strong> </p>
	 * 
	 * <p>
	 * 	Preprocessa o Padrão e cria a tabela do alfabeto, com os indices -1 caso 
	 * o elemento não se encontre no padrão e o indice no padrão caso encontre.
	 * </p>
	 * 
	 * <p>
	 * 	A tabela é criada com 256 elementos, quantidade de elementos existentes
	 * na codificação ASCII, e todos os elementos são inicializados em -1, então
	 * percorre-se a tabela com os indices numericos dos caracteres do padrão,
	 * atualizando então os valores para o indice de onde se encontram no mesmo.
	 * </p>
	 * @param p Padrão que será preprocessado.
	 */
	public void Preprocessa( String p){
		for ( int k = 0; k < 256; k++)
			this.l[ k ] = -1;
		
		for ( int k = 0; k < this.m; k++)
			this.l[  p.charAt( k )  ] = k;
	}
	
	/**
	 * 
	 * <strong>	Algoritmo de busca de Strings. </strong>
	 * <p>
	 * 	Encontra a primeira ocorrencia de um Padrão p num Texto t, evitando fazer comparações desnecessárias
	 * de acordo com o algoritmo de Boyer-Moore, e imprime o intervalo aonde foi encontrado.
	 * </p>
	 * @return Retorna -1 caso não encontre a palavra, ou i o indice da primeira letra do Padrão
	 * na primeira ocorrencia no Texto.
	 */
	public int Boyer_M2_Match(){

		Preprocessa(this.p);
		
		int i, j, l;
		
		i = j = this.m - 1;
		
		do{
			if ( this.t.charAt( i ) == this.p.charAt( j ) )
				if ( j == 0){
					System.out.println("[ " + i + ", " + ( i + this.m -1 ) + " ] ");
					return i;
				}else{
					i--;
					j--;
				}
			else{
				l = this.l[ this.t.charAt( i )  ];
				i = ( i + this.m ) - Math.min(j, ( 1 + l ) );
				j = ( this.m - 1 );
			}
		}while(i < this.n);
		return -1;
	}
}
